//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdlib.h>
#include <stdio.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int coinChange(int* coins, int coinsSize, int amount){
    int length = amount + 1;
    int* dp = (int *) malloc(sizeof(int) * length);
    dp[0] = 0;
    for (int i = 1; i < length; ++i) {
        dp[i] = length;
    }
    for (int i = 1; i < length ; ++i) {
        for (int j = 0; j < coinsSize; ++j) {
            int subProblem = i - coins[j];
            if (subProblem < 0)
                continue;
            dp[i] = min(dp[i], 1 + dp[subProblem]);
        }
    }
    return dp[amount] == length ? -1 : dp[amount];
}

static int idxCom(const void *ptrA, const void *ptrB) {
    return ((int *)ptrA)[1] - ((int *)ptrB)[1];
}

int* advantageCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    /**
     * todo
     * leetcode测试不通过，等待debugger
     */
    int n = nums1Size;
    int** idx1[n][2], idx2[n][2];
    for (int i = 0; i < n; ++i) {
        idx1[i][0] = i, idx1[i][1] = nums1[i];
        idx2[i][0] = i, idx2[i][1] = nums2[i];
    }
    qsort(idx1, n, sizeof n, idxCom);
    qsort(idx2, n, sizeof n, idxCom);
    int* res = calloc(n, sizeof n);
    *returnSize = n;
    int left = 0, right = n - 1;
    for (int i = n - 1; i >= 0; --i) {
        int maxVal1 = idx1[right][1];
        int maxVal2 = idx2[i][1];
        if (maxVal1 > maxVal2) {
            res[idx2[i][0]] = maxVal1;
            --right;
        } else {
            res[idx2[i][0]] = idx1[left][1];
            ++left;
        }
    }
    return res;
}

int main() {
    int nums1[] = {2,7,11,15};
    int nums2[] = {1,10,4,11};
    int returnSize;
    int *res = advantageCount(nums1, 4, nums2, 4, &returnSize);
    for (int i = 0; i < returnSize; ++i) {
        printf("%d ", res[i]);
    }
    return 0;
}